﻿using System;
using System.IO;
using System.Drawing;

namespace ColorReduction
{
	class K_Means
	{
		private const int COLOR_SIZE = 0x80;
		private byte[] _dataImages;
		private byte[] _centers;
		private byte[, ,] _groups = new byte[COLOR_SIZE, COLOR_SIZE, COLOR_SIZE];
		private int _kClusters;
		private int _width;
		private int _height;
		private MemoryStream _ms;
		private int _radius = 500;
		private uint[, ,] _data = new uint[COLOR_SIZE, COLOR_SIZE, COLOR_SIZE];
		private uint[, ,] _w = new uint[COLOR_SIZE, COLOR_SIZE, COLOR_SIZE];
		private K_Means() { }

		public K_Means(string _fileName, int _kClusters)
		{
			this._kClusters = _kClusters;
			this._centers = new byte[1024];
			using (FileStream sr = new FileStream(_fileName, FileMode.Open, FileAccess.Read))
			{
				using (BinaryReader br = new BinaryReader(sr))
				{
					sr.Seek(18, SeekOrigin.Begin);
					this._width = br.ReadInt32();
					this._height = br.ReadInt32();
					sr.Seek(54, SeekOrigin.Begin);
					this._dataImages = new byte[(this._width * this._height) << 2];

					int padding = (this._width % 4 == 0) ? 0 : 4 - (3 * this._width) % 4;
					int index = ((this._height - 1) * this._width) << 2;
					byte b, g, r, gr;
					for (int h = 0; h < this._height; h++)
					{
						for (int w = 0; w < this._width; w++)
						{
							b = br.ReadByte();
							g = br.ReadByte();
							r = br.ReadByte();
							gr = (byte)(0.299 * r + 0.587 * g + 0.114 * b + 0.5);
							this._dataImages[index] = b;
							this._dataImages[index + 1] = g;
							this._dataImages[index + 2] = r;
							this._dataImages[index + 3] = gr;
							this._data[b >> 1, g >> 1, r >> 1] = (uint)(b << 24) + (uint)(g << 16) + (uint)(r << 8) + (uint)gr;
							this._w[b >> 1, g >> 1, r >> 1]++;
							index += 4;
						}
						sr.Seek(padding, SeekOrigin.Current);
						index -= (this._width << 3);
					}
					//this._groups = new byte[this._width * this._height];
				}
			}
		}

		public bool Init(int _initCenters, int _radius)
		{
			this._radius = _radius;
			int i, j;
			int r, g, b;
			uint[] rc = new uint[this._kClusters];
			uint[] gc = new uint[this._kClusters];
			uint[] bc = new uint[this._kClusters];
			uint[] counts = new uint[this._kClusters];
			switch (_initCenters)
			{
				#region case 0:
				case 0:
					{
						Random random = new Random();
						for (i = 0; i < this._kClusters; i++)
						{
							j = random.Next(this._dataImages.Length >> 2);
							Buffer.BlockCopy(this._dataImages,  j << 2, this._centers, i << 2, 4);
						}

					} break;
				#endregion
				#region case 1:
				case 1:
					{
						for (b = 0; b < COLOR_SIZE; b++)
						{
							for (g = 0; g < COLOR_SIZE; g++)
							{
								for (r = 0; r < COLOR_SIZE; r++)
								{
									if (this._w[b, g, r] != 0)
									{
										this._groups[b, g, r] = (byte)(this._data[b, g, r] & 0xFF);
									}
								}
							}
						}
						
						for (b = 0; b < COLOR_SIZE; b++)
						{
							for (g = 0; g < COLOR_SIZE; g++)
							{
								for (r = 0; r < COLOR_SIZE; r++)
								{
									if (this._w[b, g, r] != 0)
									{
										bc[this._groups[b, g, r]] += ((this._data[b, g, r] >> 24) & 0xFF) * this._w[b, g, r];
										gc[this._groups[b, g, r]] += ((this._data[b, g, r] >> 16) & 0xFF) * this._w[b, g, r];
										rc[this._groups[b, g, r]] += ((this._data[b, g, r] >> 8) & 0xFF) * this._w[b, g, r];
										counts[this._groups[b, g, r]] += this._w[b, g, r];
									}
								}
							}
						}
						Array.Clear(this._centers, 0, this._centers.Length);
						for (i = 0; i < this._kClusters; i++)
						{
							if (counts[i] != 0)
							{
								j = i << 2;
								this._centers[j] = (byte)(bc[i] / counts[i]);
								this._centers[j + 1] = (byte)(gc[i] / counts[i]);
								this._centers[j + 2] = (byte)(rc[i] / counts[i]);
								this._centers[j + 3] = (byte)(0.299 * this._centers[j + 2] + 0.587 * this._centers[j + 1] + 0.114 * this._centers[j] + 0.5);
							}
						} 
					} break;
				#endregion
				#region case 2:
				case 2:
					{
						int k = 0;
						int index = 0;
						bool isnew;
						for (index = 0; index < this._dataImages.Length; index += 4)
						{
							isnew = true;

							for (i = 0; i < k; i++)
							{
								if (this.GetDist(index, i) < this._radius)
								{
									bc[i] += this._dataImages[index];
									gc[i] += this._dataImages[index + 1];
									rc[i] += this._dataImages[index + 2];
									counts[i]++;
									if (isnew == true) isnew = false;
								}
							}

							if (isnew)
							{
								for (i = 0; i < k; i++)
								{
									if (this.GetDist(index, i) < (this._radius << 1))
									{
										isnew = false;
										break;
									}
								}
							}

							if (isnew)
							{
								this._centers[k << 2] = this._dataImages[index];
								this._centers[(k << 2) + 1] = this._dataImages[index + 1];
								this._centers[(k << 2) + 2] = this._dataImages[index + 2];
								counts[k]++;
								k++;
							}
							if (k == this._kClusters) break;
						}
						
						if (k < this._kClusters) return false;
						
						for (i = 0; i < this._kClusters; i++)
						{
							j = i << 2;
							this._centers[j] = (byte)(bc[i] / counts[i]);
							this._centers[j + 1] = (byte)(gc[i] / counts[i]);
							this._centers[j + 2] = (byte)(rc[i] / counts[i]);
							this._centers[j + 3] = (byte)(0.299 * this._centers[j + 2] + 0.587 * this._centers[j + 1] + 0.114 * this._centers[j] + 0.5);
						}
					} break;
				#endregion
			}
			return true;
		}

		private int GetDist(int index, int i)
		{
			i = i << 2;
			int tmp = this._dataImages[index] - this._centers[i];
			int dist = tmp * tmp;
			tmp = this._dataImages[index + 1] - this._centers[i + 1];
			dist += tmp * tmp;
			tmp = this._dataImages[index + 2] - this._centers[i + 2];
			dist += tmp * tmp;
			return dist;
		}

		public bool Step()
		{
			bool stop = true;
			int d = 0, min, j = 0, r, g, b;
			uint[] rc = new uint[this._kClusters];
			uint[] gc = new uint[this._kClusters];
			uint[] bc = new uint[this._kClusters];
			uint[] counts = new uint[this._kClusters];
			byte r1, g1, b1, gr1;
			#region update groups
			for (b = 0; b < COLOR_SIZE; b++)
			{
				for (g = 0; g < COLOR_SIZE; g++)
				{
					for (r = 0; r < COLOR_SIZE; r++)
					{
						if (this._w[b, g, r] != 0)
						{
							b1 = (byte)((this._data[b, g, r] >> 24) & 0xFF);
							g1 = (byte)((this._data[b, g, r] >> 16) & 0xFF);
							r1 = (byte)((this._data[b, g, r] >> 8) & 0xFF);
							gr1 = (byte)(this._data[b, g, r] & 0xFF);
							min = int.MaxValue;
							for (int i = 0; i < this._kClusters; i++)
							{
								j = i << 2;
								if (gr1 - this._centers[j + 3] >= -10 && gr1 - this._centers[j + 3] <= 10)
								{
									d = (b1 - this._centers[j]) * (b1 - this._centers[j]);
									d += (g1 - this._centers[j + 1]) * (g1 - this._centers[j + 1]);
									d += (r1 - this._centers[j + 2]) * (r1 - this._centers[j + 2]);
									if (d < min)
									{
										min = d;
										this._groups[b, g, r] = (byte)i;
										stop = false;
									}
								}
							}
						}
					}
				}
			}

			#endregion

			#region update centers
			Array.Clear(this._centers, 0, this._centers.Length);

			for (b = 0; b < COLOR_SIZE; b++)
			{
				for (g = 0; g < COLOR_SIZE; g++)
				{
					for (r = 0; r < COLOR_SIZE; r++)
					{
						if (this._w[b, g, r] != 0)
						{
							bc[this._groups[b, g, r]] += ((this._data[b, g, r] >> 24) & 0xFF) * this._w[b, g, r];
							gc[this._groups[b, g, r]] += ((this._data[b, g, r] >> 16) & 0xFF) * this._w[b, g, r];
							rc[this._groups[b, g, r]] += ((this._data[b, g, r] >> 8) & 0xFF) * this._w[b, g, r];
							counts[this._groups[b, g, r]] += this._w[b, g, r];
						}
					}
				}
			}

			for (int i = 0; i < this._kClusters; i++)
			{
				if (counts[i] != 0)
				{
					j = i << 2;
					this._centers[j] = (byte)(bc[i] / counts[i]);
					this._centers[j + 1] = (byte)(gc[i] / counts[i]);
					this._centers[j + 2] = (byte)(rc[i] / counts[i]);
					this._centers[j + 3] = (byte)(0.299 * this._centers[j + 2] + 0.587 * this._centers[j + 1] + 0.114 * this._centers[j] + 0.5);
				}
			}
			#endregion
			return stop;
		}

		public void Show()
		{
			int stride = (this._width % 4 == 0) ? (this._width / 4) << 2 : (this._width / 4 + 1) << 2;
			int padding = stride - this._width;
			uint fileSize = (uint)(1078 + this._height * stride);
			if (this._ms != null) this._ms.Close();
			this._ms = new MemoryStream();
			this._ms.WriteByte((byte)0x42);
			this._ms.WriteByte((byte)0x4D);
			this._ms.Write(BitConverter.GetBytes(fileSize), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)0), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)1078), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)40), 0, 4);
			this._ms.Write(BitConverter.GetBytes(this._width), 0, 4);
			this._ms.Write(BitConverter.GetBytes(this._height), 0, 4);
			this._ms.Write(BitConverter.GetBytes((ushort)1), 0, 2);
			this._ms.Write(BitConverter.GetBytes((ushort)8), 0, 2);
			this._ms.Write(BitConverter.GetBytes((uint)0), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)this._width * this._height), 0, 4);
			this._ms.Write(BitConverter.GetBytes(3779), 0, 4);
			this._ms.Write(BitConverter.GetBytes(3779), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)1024), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)0), 0, 4);
			int i;
			for (i = 0; i < 256; i++)
			{
				this._ms.WriteByte((byte)this._centers[i << 2]);
				this._ms.WriteByte((byte)this._centers[(i << 2) + 1]);
				this._ms.WriteByte((byte)this._centers[(i << 2) + 2]);
				this._ms.WriteByte((byte)0);
			}

			byte b, g, r;
			i = ((this._height - 1) * this._width) << 2;
			for (int h = 0; h < this._height; h++)
			{
				for (int w = 0; w < this._width; w++)
				{
					b = this._dataImages[i];
					g = this._dataImages[i + 1];
					r = this._dataImages[i + 2];
					this._ms.WriteByte(this._groups[b >> 1, g >> 1, r >> 1]);
					i += 4;
				}
				if (padding != 0) this._ms.Write(new byte[padding], 0, padding);
				i -= (this._width << 3);
			}
// 			for (int h = 0; h < this._height; h++)
// 			{
// 				this._ms.Write(this._groups, index, this._width);
// 				if (padding != 0) this._ms.Write(new byte[padding], 0, padding);
// 				index -= this._width;
// 			}
			FrmPreview frmShowImage = new FrmPreview();
			frmShowImage.Show();
			frmShowImage.SetPicture(new Bitmap(this._ms));
		}

		public void ShowGray()
		{
			if (this._ms != null) this._ms.Close();
			this._ms = new MemoryStream();
			int h, w, i;
			int stride = (this._width % 4 == 0) ? (this._width / 4) << 2 : (this._width / 4 + 1) << 2;
			int padding = stride - this._width;
			uint fileSize = (uint)(1078 + this._height * stride);
			this._ms = new MemoryStream();
			this._ms.WriteByte((byte)0x42);
			this._ms.WriteByte((byte)0x4D);
			this._ms.Write(BitConverter.GetBytes(fileSize), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)0), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)1078), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)40), 0, 4);
			this._ms.Write(BitConverter.GetBytes(this._width), 0, 4);
			this._ms.Write(BitConverter.GetBytes(this._height), 0, 4);
			this._ms.Write(BitConverter.GetBytes((ushort)1), 0, 2);
			this._ms.Write(BitConverter.GetBytes((ushort)8), 0, 2);
			this._ms.Write(BitConverter.GetBytes((uint)0), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)this._width * this._height), 0, 4);
			this._ms.Write(BitConverter.GetBytes(3779), 0, 4);
			this._ms.Write(BitConverter.GetBytes(3779), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)256), 0, 4);
			this._ms.Write(BitConverter.GetBytes((uint)0), 0, 4);
			for (i = 0; i < 256; i++)
			{
				this._ms.WriteByte((byte)i);
				this._ms.WriteByte((byte)i);
				this._ms.WriteByte((byte)i);
				this._ms.WriteByte((byte)0);
			}
			int index = ((this._height - 1) * this._width) << 2;
			for (h = 0; h < this._height; h++)
			{
				for (w = 0; w < this._width; w++)
				{
					this._ms.WriteByte(this._dataImages[index + 3]);
					index += 4;
				}
					
				if (padding != 0) this._ms.Write(new byte[padding], 0, padding);
				index -= (this._width << 3);
			}
			FrmPreview frmShowImage = new FrmPreview();
			frmShowImage.Show();
			frmShowImage.SetPicture(new Bitmap(this._ms));
		}

		public void Save(string fileName)
		{
			File.WriteAllBytes(fileName, this._ms.GetBuffer());
		}
	}
}

